{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 队列的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用静态循环数组实现队列\n",
    "class Queue(object):\n",
    "    \n",
    "    def __init__(self, max_size=16):\n",
    "        self.max_size = max_size\n",
    "        self.cur_size = 0\n",
    "        self.cur_head = 0\n",
    "        self.cur_tail = 0\n",
    "        self.array = [None] * max_size\n",
    "    \n",
    "    def push(self, e):\n",
    "        if self.cur_size == self.max_size:\n",
    "            self.max_size *= 2\n",
    "            newArray = [None] * self.max_size\n",
    "            for i in range(self.cur_size):\n",
    "                newArray[i] = self.array[(self.cur_head + i) % self.cur_size]\n",
    "            self.array = newArray\n",
    "            self.cur_head = 0\n",
    "            self.cur_tail = self.cur_size\n",
    "        self.array[self.cur_tail] = e\n",
    "        self.cur_size += 1\n",
    "        self.cur_tail = (self.cur_tail + 1) % self.max_size\n",
    "        \n",
    "    def pop(self):\n",
    "        if self.cur_size == 0:\n",
    "            return None\n",
    "        e = self.array[self.cur_head]\n",
    "        self.cur_size -= 1\n",
    "        self.cur_head = (self.cur_head + 1) % self.max_size\n",
    "        return e\n",
    "        \n",
    "    def head(self):\n",
    "        return self.cur_head\n",
    "    \n",
    "    def tail(self):\n",
    "        return self.cur_tail\n",
    "        \n",
    "    def size(self):\n",
    "        return self.cur_size\n",
    "    \n",
    "    def empty(self):\n",
    "        self.cur_size = 0\n",
    "        self.cur_head = 0\n",
    "        self.cur_tail = 0\n",
    "        \n",
    "    def to_list(self):\n",
    "        if self.cur_head <= self.cur_tail:\n",
    "            return self.array[self.cur_head : self.cur_tail]\n",
    "        else:\n",
    "            return self.array[self.cur_head : ] + self.array[ : self.cur_tail]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "myqueue = Queue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'b']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.push('a')\n",
    "myqueue.push('b')\n",
    "myqueue.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 2)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.head(), myqueue.tail()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 2)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.head(), myqueue.tail()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['b']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "myqueue.push('c')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 3)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.head(), myqueue.tail()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['b', 'c']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(18):\n",
    "    myqueue.push(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['b', 'c', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(8):\n",
    "    myqueue.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 225. 用队列实现栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用队列实现栈的下列操作：\n",
    "\n",
    "push(x) -- 元素 x 入栈\n",
    "pop() -- 移除栈顶元素\n",
    "top() -- 获取栈顶元素\n",
    "empty() -- 返回栈是否为空\n",
    "\n",
    "注意:\n",
    "\n",
    "你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。\n",
    "\n",
    "你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。\n",
    "\n",
    "你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "class MyStack(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        self.deque1 = collections.deque()\n",
    "        self.deque2 = collections.deque()\n",
    "        \n",
    "    def push(self, e):\n",
    "        self.deque1.append(e)\n",
    "\n",
    "    def pop(self):\n",
    "        if len(self.deque1) == 0:\n",
    "            return\n",
    "        e = self.top()\n",
    "        self.deque1.clear()\n",
    "        self.deque1, self.deque2 = self.deque2, self.deque1\n",
    "        return e\n",
    "\n",
    "    def top(self):\n",
    "        if len(self.deque1) == 0:\n",
    "            return\n",
    "        for i in range(len(self.deque1) - 1):\n",
    "            self.deque2.append(self.deque1.popleft())\n",
    "        return self.deque1[0]\n",
    "\n",
    "    def empty(self):\n",
    "        return len(self.deque1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystack = MyStack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystack.push(1)\n",
    "mystack.push(2)\n",
    "mystack.push(3)\n",
    "mystack.push(4)\n",
    "mystack.push(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "for i in range(3):\n",
    "    print(mystack.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mystack.top()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystack.push(6)\n",
    "mystack.push(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "6\n",
      "2\n",
      "1\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    print(mystack.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mystack.empty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 232. 用栈实现队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用栈实现队列的下列操作：\n",
    "\n",
    "push(x) -- 将一个元素放入队列的尾部。\n",
    "pop() -- 从队列首部移除元素。\n",
    "peek() -- 返回队列首部的元素。\n",
    "empty() -- 返回队列是否为空。\n",
    "\n",
    "示例:\n",
    "\n",
    "MyQueue queue = new MyQueue();\n",
    "\n",
    "queue.push(1);\n",
    "queue.push(2);  \n",
    "queue.peek();  // 返回 1\n",
    "queue.pop();   // 返回 1\n",
    "queue.empty(); // 返回 false\n",
    "\n",
    "说明:\n",
    "\n",
    "你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。\n",
    "\n",
    "你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。\n",
    "\n",
    "假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "class MyQueue:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.stack1 = collections.deque()\n",
    "        self.stack2 = collections.deque()\n",
    "        \n",
    "    def push(self, e):\n",
    "        self.stack1.append(e)\n",
    "\n",
    "    def pop(self):\n",
    "        e = self.top()\n",
    "        if e:\n",
    "            self.stack2.pop()\n",
    "        return e\n",
    "\n",
    "    def top(self):\n",
    "        if len(self.stack2) == 0:\n",
    "            if len(self.stack1) == 0:\n",
    "                return\n",
    "            for i in range(len(self.stack1)):\n",
    "                self.stack2.append(self.stack1.pop())\n",
    "        return self.stack2[-1]\n",
    "\n",
    "    def empty(self):\n",
    "        return len(self.stack1) + len(self.stack2) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "myqueue = MyQueue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "myqueue.push(1)\n",
    "myqueue.push(2)\n",
    "myqueue.push(3)\n",
    "myqueue.push(4)\n",
    "myqueue.push(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "for i in range(3):\n",
    "    print(myqueue.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.top()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "myqueue.push(6)\n",
    "myqueue.push(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    print(myqueue.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myqueue.empty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 239. 滑动窗口最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。\n",
    "\n",
    "返回滑动窗口最大值。\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3\n",
    "输出: [3,3,5,5,6,7] \n",
    "\n",
    "解释: \n",
    "\n",
    "  滑动窗口的位置                最大值\n",
    "---------------               -----\n",
    "[1  3  -1] -3  5  3  6  7       3\n",
    "\n",
    " 1 [3  -1  -3] 5  3  6  7       3\n",
    " \n",
    " 1  3 [-1  -3  5] 3  6  7       5\n",
    " \n",
    " 1  3  -1 [-3  5  3] 6  7       5\n",
    " \n",
    " 1  3  -1  -3 [5  3  6] 7       6\n",
    " \n",
    " 1  3  -1  -3  5 [3  6  7]      7\n",
    " \n",
    "注意：\n",
    "\n",
    "你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。\n",
    "\n",
    "进阶：\n",
    "\n",
    "你能在线性时间复杂度内解决此题吗？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用双端队列，存入(数值，下标)，如果新元素比尾部元素大，则将尾部元素弹出，再将新元素加入尾部\n",
    "def max_sliding_window(nums, k):\n",
    "    queue = []\n",
    "    output = []\n",
    "    for idx, num in enumerate(nums):\n",
    "        while queue and queue[-1][0] <= num:\n",
    "            queue.pop()\n",
    "        queue.append((num, idx))\n",
    "        if idx == queue[0][1] + k:\n",
    "            queue.pop(0)\n",
    "        if idx >= k - 1:\n",
    "            output.append(queue[0][0])\n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 3, 5, 5, 6, 7]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_sliding_window([1,3,-1,-3,5,3,6,7], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 6, 6]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_sliding_window([7,2,6,1,3,5,4], 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[91, 55, 80, 55, 91, 12, 11, 3, 24, 12, 5, 81, 6, 12, 19, 86, 73, 5, 85, 20]\n",
      "[91, 91, 91, 91, 91, 24, 24, 81, 81, 81, 81, 86, 86, 86, 86, 86]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "test = []\n",
    "for i in range(20):\n",
    "    test.append(random.randint(0, 100))\n",
    "print(test)\n",
    "print(max_sliding_window(test, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 621. 任务调度器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。\n",
    "\n",
    "然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。\n",
    "\n",
    "你需要计算完成所有任务所需要的最短时间。\n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入: tasks = [\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"], n = 2\n",
    "输出: 8\n",
    "执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.\n",
    "\n",
    "注：\n",
    "\n",
    "任务的总个数为 [1, 10000]。\n",
    "n 的取值范围为 [0, 100]。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "# 根据字母出现次数从大到小排序\n",
    "def least_interval(tasks, n):\n",
    "    task_list = Counter(tasks).most_common()\n",
    "    seq = []\n",
    "    pointer = 0\n",
    "\n",
    "    return task_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('A', 3), ('B', 3)]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "least_interval([\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "65"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 622. 设计循环队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。\n",
    "\n",
    "循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。\n",
    "\n",
    "你的实现应该支持如下操作：\n",
    "\n",
    "MyCircularQueue(k): 构造器，设置队列长度为 k 。\n",
    "Front: 从队首获取元素。如果队列为空，返回 -1 。\n",
    "Rear: 获取队尾元素。如果队列为空，返回 -1 。\n",
    "enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。\n",
    "deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。\n",
    "isEmpty(): 检查循环队列是否为空。\n",
    "isFull(): 检查循环队列是否已满。\n",
    " \n",
    "\n",
    "示例：\n",
    "\n",
    "MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3\n",
    "\n",
    "circularQueue.enQueue(1);  // 返回 true\n",
    "\n",
    "circularQueue.enQueue(2);  // 返回 true\n",
    "\n",
    "circularQueue.enQueue(3);  // 返回 true\n",
    "\n",
    "circularQueue.enQueue(4);  // 返回 false，队列已满\n",
    "\n",
    "circularQueue.Rear();  // 返回 3\n",
    "\n",
    "circularQueue.isFull();  // 返回 true\n",
    "\n",
    "circularQueue.deQueue();  // 返回 true\n",
    "\n",
    "circularQueue.enQueue(4);  // 返回 true\n",
    "\n",
    "circularQueue.Rear();  // 返回 4\n",
    " \n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "所有的值都在 0 至 1000 的范围内；\n",
    "操作数将在 1 至 1000 的范围内；\n",
    "请不要使用内置的队列库。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyCircularQueue(object):\n",
    "    \n",
    "    def __init__(self, k):\n",
    "        self.max_size = k\n",
    "        self.size = 0\n",
    "        self.head = 0\n",
    "        self.tail = 0\n",
    "        self.array = [None] * k\n",
    "    \n",
    "    def enQueue(self, value):\n",
    "        if self.size == self.max_size:\n",
    "            return False\n",
    "        self.array[self.tail] = value\n",
    "        self.tail = (self.tail + 1) % self.max_size\n",
    "        self.size += 1\n",
    "        return True\n",
    "    \n",
    "    def deQueue(self):\n",
    "        if self.size == 0:\n",
    "            return False\n",
    "        self.head = (self.head + 1) % self.max_size\n",
    "        self.size -= 1\n",
    "        return True\n",
    "    \n",
    "    def front(self):\n",
    "        if self.size == 0:\n",
    "            return -1\n",
    "        return self.array[self.head]\n",
    "    \n",
    "    def rear(self):\n",
    "        if self.size == 0:\n",
    "            return -1\n",
    "        if self.tail == 0:\n",
    "            return self.array[self.max_size - 1]\n",
    "        return self.array[self.tail - 1]\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.size == 0\n",
    "    \n",
    "    def isFull(self):\n",
    "        return self.size == self.max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "circularQueue = MyCircularQueue(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circularQueue.enQueue(1)\n",
    "circularQueue.enQueue(2)\n",
    "circularQueue.enQueue(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circularQueue.enQueue(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circularQueue.rear()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circularQueue.isFull()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circularQueue.deQueue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circularQueue.enQueue(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circularQueue.rear()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
